COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00007 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a14.tex[162,phy] \today\hfill}

\def\indeq{\buildrel {\rm ind}\over =}%ind over =

\parskip 5pt
\bigskip
\line{\bf A Generalized Binomial Theorem\hfill}

Hold $h$ fixed. Define $x↑{\underline{\underline{n}}}$ as 
$x(x+h)(x+2h)\ldots\,$, $n$~terms. Special cases:
$$\vcenter{\halign{$#\;$&$#$\qquad&$#$\cr
h&=0&x↑n\cr
h&=1&x↑{\overline{n}}\cr
h&=-1&x↑{\underline{n}}\cr}}$$

\line{{\bf Theorem,} generalizing Knuth, Example 1.2.6--33:\hfil}

$$(x+y)↑{\underline{\underline{n}}}\;=\sum↓i{n\choose i}\,
x↑{\underline{\underline{i}}}\,y↑{\underline{\underline{n-i}}}\,.$$

\line{{\bf Proof.} By induction,\hfil}

$$\eqalign{\sum↓i{n+1\choose i}\,x↑{\underline{\underline{i}}}\,
y↑{\underline{\underline{n+1-i}}}
&=\sum↓i\biggl({n\choose i}+{n\choose i-1}\bigg)\,x↑{\underline{\underline{i}}}\,
y↑{\underline{\underline{n+1-i}}}\cr
\noalign{\smallskip}
&=\sum↓i{n\choose i}\,x↑{\underline{\underline{i}}}\,
y↑{\underline{\underline{n+1-i}}}+\sum↓i{n\choose i}\,
x↑{\underline{\underline{i+1}}}\,y↑{\underline{\underline{n-i}}}\cr
\noalign{\smallskip}
&=\sum↓i{n\choose i}\,x↑{\underline{\underline{i}}}\,
y↑{\underline{\underline{n-i}}}\bigl((x+ih)+(y+(n-1)h)\bigr)\cr
\noalign{\smallskip}
&=(x+y+nh)\sum↓i{n\choose i}\,x↑{\underline{\underline{i}}}\,
y↑{\underline{\underline{n-i}}}
\indeq (x+y+nh)(x+y)↑{\underline{\underline{n}}}\cr
\noalign{\smallskip}
&=(x+y)↑{\underline{\underline{n+1}}}\,.\qquad\blackslug\cr}$$

Thanks to D. Knuth for suggesting the generalization to $h$ arbitrary.
Important special cases:
$$\eqalign{(x+y)↑n&=\sum{n\choose i}\,x↑i\,y↑{n-i}\qquad\hbox{binomial theorem}\cr
\noalign{\smallskip}
(x+y)↑{\overline{n}}&=\sum{n\choose i}\,x↑{\overline{i}}\,
y↑{\overline{n-i}}\cr
\noalign{\smallskip}
(x+y)↑{\underline{n}}&=\sum{n\choose i}\,x↑{\underline{i}}\,
y↑{\underline{n-i}}\cr}$$

Another instance, probably unimportant.
$P=(2a+1)(2a+3)(2a+5)\ldots\,$, $n$ terms.
Set $h=2$, $x=2a$, $y=1$;
$P=\sum↓i{n\choose i}\,a↑i(2\cdot 6\cdot 10\,\ldots\,$,
$n-i$ terms.)

\smallskip
\disleft 38pt::
{\bf Exercise.} Find a dissection of an $n$-dimensional rectangular solid
that embodies the theorem.


\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd.
First draft (not published)
January 13, 1987.
%revised date;
%subsequently revised.

\bye